#include <iostream>
#include <string.h>

using std::cout;
using std::endl;

template<typename T>
class Stack{
public:
    Stack():top_(-1), cap_(10), arr_(new T[cap_]){}
    ~Stack(){}

    void push(T data) 
    {
        if(top_ == cap_ - 1){
            expand();
        }
        arr_[++top_] = data;
    }

    bool empty() const
    {
        return top_ == -1;
    }

    T top() const
    {
        if(empty())
            throw "stack is empty()";

        return arr_[top_];
    }

    void pop()
    {
        if(empty())
            throw "stack is empty()";
        --top_;
    }

private:
    void expand()
    {
        cap_ = cap_ * 2;
        T *tmp = new T[cap_];
        memcpy(tmp, arr_, (top_ + 1) * sizeof(T));
        delete [] arr_;
        arr_ = tmp;
    }

private:
    int top_;
    size_t cap_;
    T *arr_;
};

template<typename T>
struct Node{
    T data;
    Node *next;
    Node *pre;

    Node():data(0), next(nullptr), pre(nullptr){}
    Node(int dt): data(dt), next(nullptr), pre(nullptr){}
    Node(int dt, Node *pe, Node *nt): data(dt), pre(pe), next(nt){}
};

template<typename T>
class LStack{
public:
    LStack():head_(new Node<T>()), top_(head_){}
    ~LStack()
    {
        while(head_){
            Node<T> *next = head_;
            head_ = head_->next; 
            delete next;
        }
    }

    bool empty() const
    {
        return top_ == head_;
    }

    void push(T data)
    {
        Node<T> *cur = new Node<T>(data, top_, nullptr);
        top_->next = cur;
        top_ = cur;
    }

    T top() const
    {
        if(empty())
            throw "stack is empty()";
        return top_->data;
    }

    void pop()
    {
        if(empty())
            throw "stack is empty()";
        
        Node<T> *pre = top_->pre;
        delete top_;
        top_ = pre;
        top_->next = nullptr;
    }

private:
    Node<T> *head_;
    Node<T> *top_;
};

void test1()
{
    int arr[] = {1, 2, 3, 4, 5, 0, 5, 5, 6, 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 1, 1};
    Stack<int> stack;

    for(int i: arr){
        stack.push(i);
    }

    while(!stack.empty()){
        printf("%d ", stack.top());
        stack.pop();
    }
}

int main(int args, char *argv[])
{
    test1();
    return 0;
}